\documentclass{beamer}

\mode<presentation>
{
  \usetheme{Warsaw}
  \setbeamercovered{transparent}
}


\usepackage[english,russian]{babel}
\usepackage[utf8x]{inputenc}
\usepackage{times}
\usepackage[T1]{fontenc}

\newcommand{\setblue}[1]{\textcolor{blue!50!black}}
\newcommand{\setgreen}[2]{\textcolor{green!50!black}}

\title[Индексы роста бесстепенных языков]
{Оценки индексов роста и границ\\
повторяемости для бесстепенных языков}

\author[Алексей Самсонов] % (optional, use only with lots of authors)
{Алексей Самсонов}

\institute[Уральский федеральный университет] % (optional, but mostly needed)
{
  Уральский федеральный университет\\
  Математико-механический факультет}

\date[08.06.2010] % (optional, should be abbreviation of conference name)
{8 июня, 2011}


% If you have a file called "university-logo-filename.xxx", where xxx
% is a graphic format that can be processed by latex or pdflatex,
% resp., then you can add a logo as follows:

\pgfdeclareimage[height=0.5cm]{university-logo}{usu_symbol}
\logo{\pgfuseimage{university-logo}}


%\AtBeginSection[]
%{
%  \begin{frame}<beamer>{Outline}
%    \tableofcontents[currentsection,currentsubsection]
%  \end{frame}
%}

\begin{document}

\begin{frame}
  \titlepage
\end{frame}

%\begin{frame}{Outline}
%  \tableofcontents
%\end{frame}

\section{Предварительные сведения}

\begin{frame}{Экспоненты слов}
	\begin{itemize}
		\item \alert{Экспонента} слова~--- отношение длины слова к его минимальному периоду.
		\item Если \textcolor{blue}{$\beta$}~--- экспонента слова \textcolor{blue}{$u$},
			то \textcolor{blue}{$u$} является \alert{$\beta$-степенью}.
	\end{itemize}
	\begin{block}{Примеры}
		\begin{itemize}
			\item Экспонента слова \alert{templa te}~--- \textcolor{blue}{4/3}.
			\item Экспонента слова \alert{abc abc a}~--- \textcolor{blue}{7/3}.
		\end{itemize}
	\end{block}
	\begin{block}{Замечание}<2->
		Если \textcolor{blue}{$u$}~--- \textcolor{blue}{$\beta$}-степень, \textcolor{blue}{$\beta < 2$},
			то \textcolor{blue}{$u = xyx$}, \textcolor{blue}{$xy$}~--- \alert{корень} слова \textcolor{blue}{$u$}.
	\end{block}
\end{frame}

\begin{frame}{Языки с ограниченной экспонентой}
	\begin{itemize}
		\item Слово \textcolor{blue}{$u$} является \alert{$\beta$-свободным},
			если экспоненты всех его подслов меньше \textcolor{blue}{$\beta$}.
		\item Экспонента \textcolor{blue}{$\beta$} \alert{$k$-избегаема}, если существует бесконечно много \textcolor{blue}{$\beta$}-свободных слов
			над \textcolor{blue}{$k$}-буквенным алфавитом, и \alert{$k$-неизбежна} в противном случае.
		\item \alert{Граница повторяемости}~--- это число \alert{$RT(k)$}, разделяющее \textcolor{blue}{$k$}-неизбежные
			и \textcolor{blue}{$k$}-избегаемые экспоненты.
	\end{itemize}
	\begin{block}{Гипотеза[Дежан, 1972; доказана в 2010]}<2->
		\begin{itemize}
			\item \textcolor{blue}{$RT(3) = 7/4$},
			\item \textcolor{blue}{$RT(4) = 7/5$},
			\item \textcolor{blue}{$RT(k) = k/(k-1)$} для всех \textcolor{blue}{$k \geqslant 5$}.
		\end{itemize}
	\end{block}
\end{frame}

\begin{frame}{Индексы роста}
	\begin{itemize}
		\item \alert{Комбинаторная сложность} языка \textcolor{blue}{$L$}~--- это функция
			\textcolor{blue}{$C_L(n) = |\Sigma^n\cap L|$}.
		\item \alert{Индекс роста} \textcolor{blue}{$L$} определяется как
			\textcolor{blue}{$\alpha(L) = \limsup\limits_{n\to\infty}(C_L(n))^{1/n}$}.
		\item \textcolor{blue}{$\alpha(L) = 0$}, если язык конечен, \textcolor{blue}{$\alpha(L) > 1$} для языков
			с экспоненциальным ростом.
	\end{itemize}
	\begin{block}{Замечание}<2->
		Мы вычисляем \alert{верхние границы} индексов роста языков с ограниченной экспонентой.
	\end{block}
\end{frame}

\begin{frame}{Антисловари}
	\begin{itemize}
		\item \alert{Антисловарь $M$} языка \textcolor{blue}{$L$}~--- это множество минимальных
			(относительно взятия подслов) запрещённых в \textcolor{blue}{$L$} слов.
		\item \textcolor{blue}{$M=\Sigma L\cap L\Sigma\cap(\Sigma^*{-}L)$}
		\item \textcolor{blue}{$L=\Sigma^*-\Sigma^*\!M\Sigma^*$}
	\end{itemize}
	\begin{block}{Замечание}<2->
		Антисловари бесконечных языков с ограниченной экспонентой \alert{бесконечны}.
	\end{block}
\end{frame}

\begin{frame}{Основной метод}
	Общая схема вычисления верхних оценок индексов роста описана в
	\textcolor{green!50!black}{[Shur, Growth rates of complexity of power free-languages, Theor. Comp. Sci., 2010]}:
	\begin{enumerate}
		\item<2-> Построить \alert{конечное приближение} \textcolor{blue}{$\bar{M}$} антисловаря \textcolor{blue}{$M$}.
		\item<2-> Построить \alert{автомат} \textcolor{blue}{$\cal A$}, распознающий язык, заданный \textcolor{blue}{$\bar{M}$}.
		\item<2-> Верхняя оценка равна \alert{корню Фробениуса} матрицы смежности \textcolor{blue}{$\cal A$}.
	\end{enumerate}
	\begin{block}{Замечание}<3->
		Построение антисловаря является \alert{наиболее трудоёмкой} задачей.
	\end{block}
\end{frame}

\section{Языки первого уровня}

\begin{frame}{Антисловари языков первого уровня}
	\textcolor{blue}{$L$}~--- \textcolor{blue}{$\beta$}-свободный язык \alert{первого уровня} над
	\textcolor{blue}{$k$}-буквенным алфавитом, если	\textcolor{blue}{$RT(k) < \beta \leq \frac{k-1}{k-2}$}.
	\begin{itemize}
		\item<2-> Реализована эффективная проверка того, является ли запрещённое слово \textcolor{blue}{$xyx$} с корнем
		\textcolor{blue}{$xy$} \alert{минимальным} запрещённым (на практике~--- за \alert{линейное} время).
		\item<2-> Потенциальные корни запрещённых слов перебираются рекурсивно.
		\item<2-> Вспомогательные структуры данных (\alert{суффиксный массив}) занимают существенно меньше памяти,
			чем построенный антисловарь.
		\item<2-> Найденные запрещённые слова хранятся в \alert{двоичном} коде Пансьё.
	\end{itemize}
\end{frame}

\begin{frame}{Результаты экспериментов}
	\begin{itemize}
		\item Создан универсальный инструмент вычисления оценок индексов роста языков первого уровня.
		\item Объёмы построенных антисловарей достигают \alert{$80$ млн.} символов.
		\item Полученные оценки отличаются от реальных значений индексов роста на величину \alert{от $5\cdot10^{-4}$ до $10^{-6}$}.
	\end{itemize}
\end{frame}

\section{Абелевы степени}

\begin{frame}{Целые абелевы степени}
	\begin{itemize}
		\item Слово \textcolor{blue}{$u_1u_2 \ldots u_n$} является \alert{абелевой $n$-й степенью}, если слова
			\textcolor{blue}{$u_2$}, \ldots, \textcolor{blue}{$u_n$} являются анаграммами \textcolor{blue}{$u_1$}.
		\item Для \alert{частотных векторов} мы можем записать \textcolor{blue}{$\vec p(u_1) = \ldots = \vec p(u_n)$}.
	\end{itemize}
	\begin{block}{Примеры}<2->
		\begin{itemize}
			\item \alert{acab bcaa} ~--- абелев \textcolor{blue}{квадрат}.
			\item \alert{abba abab baba}~--- абелев \textcolor{blue}{куб} и абелев \textcolor{blue}{квадрат}.
		\end{itemize}
	\end{block}
\end{frame}

\begin{frame}{Дробные абелевы степени}
	Пусть \textcolor{blue}{$\beta > 1$}. \textcolor{blue}{$u = u_1u_2 \ldots u_mv$}~--- это
		\alert{абелева $\beta$-степень}, если:
	\begin{itemize}
		\item \textcolor{blue}{$\vec p(u_1) = \vec p(u_2) = \ldots = \vec p(u_m)$},
			\textcolor{blue}{$m = \lfloor \beta \rfloor$},
			\textcolor{blue}{$u_1$} называется \alert{корнем};
		\item \textcolor{blue}{$|v| = \lceil \{\beta\}|u_1| \rceil$},
			\textcolor{blue}{$v$} называется \alert{хвостом};
		\item Каковы ограничения на \textcolor{blue}{$\vec p(v)$}?
	\end{itemize}
	\begin{block}{}
		\begin{itemize}
			\item<2-> \alert{Слабые} степени: \textcolor{blue}{$\vec p(v) \leqslant \vec p(u_1)$},
				т.е. хвост~--- это \alert{префикс анаграммы корня}.
			\item<3-> \alert{Строгие} степени: \textcolor{blue}{$\vec p(v) = \vec p(\mathrm{pref}(u_1, |v|))$},
				т.е. хвост~--- это \alert{анаграмма префикса корня}.
			\item<4-> \alert{Полустрогие} степени:
				\textcolor{blue}{$\vec p(v) \leqslant \bigvee\limits_{i=\overline{1,m}}\!\!\vec p(\mathrm{pref}(u_i,|v|))$}, где
				\textcolor{blue}{$\bigvee$}~--- это \alert{покомпонентный максимум}.
		\end{itemize}
	\end{block}
\end{frame}

\begin{frame}{Примеры дробных абелевых степеней}
	\begin{itemize}
		\item \alert{bana na}~--- слабая (но не строгая или полустрогая) абелева \textcolor{blue}{$(3/2)$}-степень.
		\item \alert{abc cba ac}~--- слабая и полустрогая (но не строгая) абелева \textcolor{blue}{$(8/3)$}-степень.
		\item \alert{baob ab}~--- слабая, полустрогая и строгая абелева \textcolor{blue}{$(3/2)$}-степень.
	\end{itemize}
\end{frame}

\begin{frame}{Абелева граница повторяемости}
	Для абелевых экспонент можно аналогично определить \alert{абелево $\beta$-свободные языки} и \alert{абелеву границу
	повторяемости}.
	\begin{block}{Теорема 4.4}<2->
		\textcolor{blue}{$ART_s(k) \geq \frac{k-2}{k-3}$} для всех \textcolor{blue}{$k \geq 5$}.
	\end{block}
	\begin{block}{Теорема 4.8}<3->
		\textcolor{blue}{$ART_w(k) \geq \frac{k}{k-2}$} для всех \textcolor{blue}{$k \geq 10$}.
	\end{block}
\end{frame}

\begin{frame}{Антисловари абелево $\beta$-свободных языков}
	Разработан \alert{алгоритм} построения антисловарей абелево \textcolor{blue}{$\beta$}-свободных языков:
	\begin{enumerate}
		\item Потенциальные корни запрещённых слов перебираются в порядке возрастания их длин.
		\item Для каждого корня генерируются \alert{все запрещённые слова} с таким корнем и проверяются на минимальность.
		\item Антисловари абелево \textcolor{blue}{$\beta$}-свободных языков сравнительно велики и содержат много <<длинных>> слов.
	\end{enumerate}
\end{frame}

\begin{frame}{Результаты экспериментов}
	Вычислены оценки индексов роста абелево \textcolor{blue}{$\beta$}-свободных языков для различных экспонент и
	определений дробных абелевых степеней.
	\begin{block}{Гипотеза}<2->
		Абелева граница повторяемости \alert{совпадает} для случая \alert{строгих} и \alert{полустрогих} степеней.
	\end{block}
	\begin{block}{Гипотеза 4.18[Samsonov, Shur, 2010]}<3->
		\begin{itemize}
			\item \textcolor{blue}{$ART_s(2) = 11/3$},
			\item \textcolor{blue}{$ART_s(3) = 2$},
			\item \textcolor{blue}{$ART_s(4) = 9/5$},
			\item \textcolor{blue}{$ART_s(k) = (k-2)/(k-3)$} для \textcolor{blue}{$k \geqslant 5$}.
		\end{itemize}
	\end{block}
\end{frame}

\begin{frame}
\centerline{\alert{Спасибо за внимание!}}
\end{frame}


\end{document}